House Robber II

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

Solution:

  1. public class Solution {
  2.   public int rob(int[] nums) {
  3.     if (nums == null || nums.length == 0)
  4.       return 0;
  6.     int n = nums.length;
  8.     if (n == 1) 
  9.       return nums[0];
  11.     if (n == 2) 
  12.       return Math.max(nums[0], nums[1]);
  14.     return Math.max(rob(nums, 0, n - 2), rob(nums, 1, n - 1));
  15.   }
  17.   int rob(int[] nums, int s, int e) {
  18.     int n = e - s + 1;
  20.     int[] dp = new int[n + 1];
  21.     dp[1] = nums[s];
  23.     for (int i = 2; i <= n; i++) {
  24.       dp[i] = Math.max(dp[i - 1], nums[s - 1 + i] + dp[i - 2]);
  25.     }
  27.     return dp[n];
  28.   }
  29. }